{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 什么是动态规划?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 动态规划\n",
    "动态规划：本质上也是一种暴力求解，不直接去处理问题，而是在每一步处理问题进程中，运用曾经的状况以及当时状况的状况而抵达一个当时的最优状况.\n",
    "\n",
    "规划：在一般处理该类问题的时分，会有一个“填表格”的进程，不论是简略状况下的一维表格仍是杂乱一点的二维表格，都是以开荒空间换时刻的思想，以争夺最佳的时刻功率. （保存进程中心值，便利后续直接运用）.  \n",
    "因此动态规划通常有一个dp数组, **一般状况dp数组用来保存从开始到当时状况的最优值，故而保存的是截止到现在的最优值，防止重复核算.**\n",
    "### 1.2 动态规划vs递归\n",
    "![](img/动态规划-斐波那契.png)  \n",
    "计算斐波那契数列时: fib(N-1) + fib(N-2)，如果用递归会有重复运算。如上图：相同颜色的节点即为重复运算。\n",
    "### 1.3 动态规划问题的特性\n",
    "- 最优化原理  \n",
    "如果原问题的最优解所分解出的子问题的解也是最优的，我们就称该问题具有最优子结构，原问题的最优解可以有子问题的最优解推导得出；  \n",
    "- 无后效性  \n",
    "某阶段状态一旦确定，这个状态以后决策的影响，它只与当前状态有关；  \n",
    "- 有重叠子问题  \n",
    "子问题可能会在下一阶段决策中被重复多次用到。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 动态规划子问题拆解案例"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### 2.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 [最长递增子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/)\n",
    "#### 场景:      \n",
    "给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。  \n",
    "示例：  \n",
    "输入：nums = [10,9,2,5,3,7,101,18]   \n",
    "输出：4   \n",
    "解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。   \n",
    "#### 题解1:  \n",
    "- d[i]为**以nums[i]结尾**的最长严格递增子序列长度\n",
    "- d[i]初始值为1\n",
    "- d[i]=max([d[j] + 1 for j in range(0, i) if nums[i] > nums[j]] + [1])\n",
    "- 最终结果: max(d)  \n",
    "\n",
    "#### 题解2:\n",
    "- tails[k]为**长度为k递增子序列中末尾值最小的值**, max_length为当前\n",
    "- tails[0]\n",
    "- 更新:  \n",
    "寻找: k = min{k | tails[k] > nums[i], i <= max_length}   \n",
    "如果存在, 更新: tails[k] = nums[k]   \n",
    "如果不存在, 更新: max_length += 1；tails[max_length] = nums[i]\n",
    "- 维护一个当前最大的序列长度变量, max_length\n",
    "        - 维护一个tails表, tails[k]表示长度为k+1的所有序列中, 末尾值最小的值 --同样长度的序列, 末位置小的序列后续成长空间更大, 成长空间是大的的父集\n",
    "        寻找d[i]的步骤:\n",
    "        1)寻找: k = min{k | tails[k] > nums[i], i <= max_length}\n",
    "        2)如果存在, 更新: tails[k] = nums[k]\n",
    "        3)如果不存在, 更新:\n",
    "                        max_length += 1\n",
    "                        tails[max_length] = nums[i]\n",
    "                        \n",
    "\n",
    "### 2.2 [最大子序和](https://leetcode-cn.com/problems/maximum-subarray/)\n",
    "#### 场景\n",
    "给定一个整数数组nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。  \n",
    "示例:  \n",
    "示例 1： \n",
    "输入：nums = [-2,1,-3,4,-1,2,1,-5,4]  \n",
    "输出：6   \n",
    "解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。  \n",
    "#### 题解:  \n",
    "- d[i]为**以nums[i]结尾**的最大子序和\n",
    "- d[i]初始值为nums[i]\n",
    "- d[i+1] = max(d[i], d[i] + nums[i])\n",
    "- 最终结果: max(d)  \n",
    "\n",
    "### 2.3 [编辑距离](https://leetcode-cn.com/problems/edit-distance/)\n",
    "#### 场景\n",
    "给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。\n",
    "> 你可以对一个单词进行如下三种操作：  \n",
    " 插入一个字符   \n",
    " 删除一个字符   \n",
    " 替换一个字符   \n",
    " 示例 1：   \n",
    " 输入：word1 = \"horse\", word2 = \"ros\"   \n",
    " 输出：3  \n",
    " 解释：  \n",
    " horse -> rorse (将 'h' 替换为 'r')  \n",
    " rorse -> rose (删除 'r')  \n",
    " rose -> ros (删除 'e')  \n",
    " 示例 2：   \n",
    " 输入：word1 = \"intention\", word2 = \"execution\"   \n",
    " 输出：5  \n",
    " 解释：  \n",
    " intention -> inention (删除 't')   \n",
    " inention -> enention (将 'i' 替换为 'e')   \n",
    " enention -> exention (将 'n' 替换为 'x')   \n",
    " exention -> exection (将 'n' 替换为 'c')   \n",
    " exection -> execution (插入 'u')  \n",
    "\n",
    "#### 题解\n",
    "- d[i][j]为s1前i个字符和s2前j个字符的编辑距离\n",
    "- d[0][:] = 1, d[:][0] = 1, d[0][0] = 0\n",
    "- 更新\n",
    "- - if s1[i] == s2[j]: d[i+1][j+1] = d[i][j]\n",
    "- - else: d[i+1][j+1] = min(d[i][j+1]+1, d[i+1][j]+1, d[i][j]+1)\n",
    "- 最终结果: d[len(s1)][len(s2)]\n",
    "\n",
    "### 2.4 [最长回文字串](https://leetcode-cn.com/problems/longest-palindromic-substring/)\n",
    "#### 场景\n",
    "给你一个字符串 s，找到 s 中最长的回文子串。\n",
    "\n",
    "示例 1：  \n",
    "\n",
    "输入：s = \"babad\"  \n",
    "输出：\"bab\"  \n",
    "解释：\"aba\" 同样是符合题意的答案。  \n",
    "示例 2：  \n",
    "输入：s = \"cbbd\"  \n",
    "输出：\"bb\"  \n",
    "示例 3： \n",
    "输入：s = \"a\"  \n",
    "输出：\"a\"  \n",
    "示例 4：  \n",
    "输入：s = \"ac\"  \n",
    "输出：\"a\"  \n",
    "\n",
    "#### 题解\n",
    "- d[i][j]为s[i:j]为回文字符串\n",
    "- d[i][i+1]=True\n",
    "- d[i][j] = d[i-1][j+1] and s[i] == s[j]\n",
    "- 注意d[i][j]依赖i-1,j+1的状态, 因此遍历时可以按len从0到1遍历  \n",
    "\n",
    "### 2.5 [最长公共子序列](https://leetcode-cn.com/problems/qJnOS7/)\n",
    "#### 场景\n",
    "> 给定两个字符串text1和text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0。\n",
    "一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。\n",
    "例如，\"ace\" 是 \"abcde\" 的子序列，但 \"aec\" 不是 \"abcde\" 的子序列。\n",
    "两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。\n",
    "示例 1：\n",
    "输入：text1 = \"abcde\", text2 = \"ace\" \n",
    "输出：3  \n",
    "解释：最长公共子序列是 \"ace\" ，它的长度为 3 。\n",
    "示例 2：\n",
    "输入：text1 = \"abc\", text2 = \"abc\"\n",
    "输出：3\n",
    "解释：最长公共子序列是 \"abc\" ，它的长度为 3 。\n",
    "示例 3：\n",
    "输入：text1 = \"abc\", text2 = \"def\"\n",
    "输出：0\n",
    "解释：两个字符串没有公共子序列，返回 0 。\n",
    "\n",
    "#### 题解\n",
    "- d[i][j]表示s1[:i]和s2[:j]的公共子序列\n",
    "- 初始化if i < 0 or j < 0: 0\n",
    "- if s1[i] == s2[j]: d[i-1][j-1] + 1\n",
    "- else: max(d[i-1][j], d[i][j-1])\n",
    "- 结果: d[-1][-1]\n",
    "\n",
    "### 2.6 [最长公共字串]\n",
    "#### 场景\n",
    "*和上一个相似, 只是子串需要连续*\n",
    "\n",
    "#### 题解\n",
    "- if i < 0 or j < 0: 0\n",
    "- if s1[i] == s2[j]: d[i-1][j-1] + 1\n",
    "- else: 0\n",
    "- 结果: max(d[i][j])\n",
    "\n",
    "### 2.7 [打家劫舍](https://leetcode-cn.com/problems/house-robber/)\n",
    "#### 场景\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考\n",
    "[1]https://www.6hu.cc/archives/10620.html   \n",
    "[2]https://www.cnblogs.com/kubidemanong/p/11854724.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
